[JS/백준]{dp}(11053) 가장 긴 증가하는 부분 수열

문제 설명

dp문제로 0 ~ n까지 for문으로 돌면서 0에서부터 i-1번쨰 값까지 비교한다 arr[i]번쨰 값 앞에

arr[i]번쨰 값보다 작은 값이 있을경우 현재 dp[i]의 값과 dp[j] + 1 값을 비교해서 더 큰 값을

넣어서 최대 수열의 길이를 찾을수 있도록 비교한다.

밑에 사진을 보면 index 3번째 값을 0부터 2번째 비교해서 더 작은 값이 있을 경우 dp[i] 값을

더 큰 값으로 갱신해준다 dp[2]번째 값도 dp[3]보다 작지만 최대 길이를 만족하지 않기 때문에

무시해준다.

코드

let input = require("fs")
  .readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const n = +input[0];
const arr = input[1].split(" ").map(Number);

const dp = Array(n).fill(1);
let maxVal = 1;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < i; j++) {
    if (arr[i] > arr[j]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
      if (dp[i] > maxVal) {
        maxVal = dp[i];
      }
    }
  }
}
console.log(maxVal);